Q1. linked list是什麼

• 是一種資料結構，透過很多節點(Node)串接成一個 linked list 型態的資料。
• 以 python 宣告的 ListNode class 為例

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

• 你可以在 python 中宣告一個名為 linked_data 的 ListNode 結構(沒有給參數，則根據 ListNode 預設值創建)，宣告一個名為 data_1 的 ListNode 結構，val 為 1

linked_data = ListNode()
data_1 = ListNode(1)

linked_data.next = data_1 

• 畫出來的型態如下圖
  

• linked list 的資料結構可以實作新增、刪除的功能

  • 刪除 linked list中的一個，只需要將指向下一個節點 next 修改成要指向的新 node

  

  • 新增的功能，只要將新增的Node指向即將插入的後一個 Node，然後再讓前一個 Node 指向新Node

    

• python 中 linked list vs. list vs. array

  • linked list 通常是自己宣告節點需要哪些資料，若你希望你的 linked list 可以具備往上一個 Node 跳的功能，那你也可以在 class 新增一個 pre，專門指向前一個 Node，形成 doubly linked link。

    # 宣告一個結構
    class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next
    
    # 宣告一個命名為 linked_data 的 ListNode class 結構的資料 
    linked_data = ListNode()
    
    

  • list

    • 我們平常使用的 List 結構，就會跟記憶體要一連串的位址，如圖 0x310718~0x3106e8 位址，每個位址會儲存真正的，指向真正儲存的值的位址，假設讀取 list 最後一個位址 (0x3106e8)，他會導向真正儲存值的地方，找到我們儲存的資料

      

    • 有人就會有疑問了，為什麼不直接把資料儲存在跟記憶體要的空間，而是還要儲存一個位置，導向真正的資料位置，list 這樣設計的好處是，他是儲存「真正一筆資料的位址」，所以資料可以不限制類型，可以是字串、數字...，儲存的不同類型資料會額外分配空間，而list 只要記錄地址就可以，這樣我們一開始分配 list 空間的時候，就不會忽大忽小，不過也是因為導向的關係，所以 List 效率會比較低

    • 切記，若我們想將 list 中間把資料砍掉，例如 0x310700 的值不要了，那麼 0x3106b8~0x3106e8 就會向前遞補，0x310700~0x3106d0 就會儲存新導向的地方

  • numpy array (額外使用 numpy library)

    • 跟記憶體要一段空間，空間直接儲存資料，array 中，只能儲存相同型態的資料

      

圖片來自 https://medium.com/@t0915290092/如何解決-pandas-效率緩慢的問題-7466b3e996df

Q2. 所以學會 linked list 概念可以做什麼 ?

• 由於新增跟刪除很快，不需要將後面的資料逐漸遞補，所以在追求效率新增、刪除資料上，可以使用 linked list 的概念

Lab. 明天要分析的題目： 24. Swap Nodes in Pairs

題目連結：https://leetcode.com/problems/swap-nodes-in-pairs/

題目敘述：

• 你必須改變兩兩相鄰節點的位置，例如 [1,2,3,4] 你必須改成 [2,1,4,3]
• 必須改變位置，不能改變 val 值

測資的 Input/Output：

• input 你會得到 linked list 的頭 (你可以直接 .val 或是 .next 看下一個點)

• 你必須回傳一個交換過的 linked list 的頭

  

題目的條件：

• node 會有 0~100個

• 每個 node 的 val 會介於 0~100

  

• 看完題目，你要思考：

  • 若 input 為 [1,2,3] 那麼 output 預設為 [2,1,3] 還是 [1,3,2] ?